{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #在每个树行中找最大值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestValues"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #在每个树行中找最大值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一棵二叉树的根节点&nbsp;<code>root</code> ，请找出该二叉树中每一层的最大值。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>root = [1,3,2,5,3,null,9]\n",
    "<strong>输出: </strong>[1,3,9]\n",
    "<strong>解释:</strong>\n",
    "          1\n",
    "         / \\\n",
    "        3   2\n",
    "       / \\   \\  \n",
    "      5   3   9 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>root = [1,2,3]\n",
    "<strong>输出: </strong>[1,3]\n",
    "<strong>解释:</strong>\n",
    "          1\n",
    "         / \\\n",
    "        2   3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>root = [1]\n",
    "<strong>输出: </strong>[1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>root = [1,null,2]\n",
    "<strong>输出: </strong>[1,2]\n",
    "<strong>解释:</strong>      \n",
    "&nbsp;          1 \n",
    "&nbsp;           \\\n",
    "&nbsp;            2     \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例5：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>root = []\n",
    "<strong>输出: </strong>[]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>二叉树的节点个数的范围是 <code>[0,10<sup>4</sup>]</code></li>\n",
    "\t<li><meta charset=\"UTF-8\" /><code>-2<sup>31</sup>&nbsp;&lt;= Node.val &lt;= 2<sup>31</sup>&nbsp;- 1</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 515&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/\">https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [hPov7L](https://leetcode.cn/problems/hPov7L/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [hPov7L](https://leetcode.cn/problems/hPov7L/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,2,5,3,null,9]', '[1,2,3]', '[1]', '[1,null,2]', '[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        level = [root]\n",
    "        res = []\n",
    "        while level:\n",
    "            tmp = -float('inf')\n",
    "            newlevel = []\n",
    "            for x in level:\n",
    "                tmp = max(tmp, x.val)\n",
    "                if x.left:\n",
    "                    newlevel.append(x.left)\n",
    "                if x.right:\n",
    "                    newlevel.append(x.right)\n",
    "            level = newlevel\n",
    "            res.append(tmp)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    " \n",
    "        res = [ ]\n",
    "        ans = []\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            q = len(queue)\n",
    "            ans = []\n",
    "            for i in range(q):\n",
    "                node = queue.pop(0)\n",
    "                ans.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(max(ans))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    " \n",
    "        res = [ ]\n",
    "        ans = []\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            q = len(queue)\n",
    "            ans = []\n",
    "            for i in range(q):\n",
    "                node = queue.pop(0)\n",
    "                ans.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(max(ans))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        max_value = []\n",
    "        if root is None:\n",
    "            return max_value\n",
    "        q, head = [root], -1\n",
    "        level = [0]\n",
    "        max_value.append(root.val)\n",
    "        while head < len(q) - 1:\n",
    "            head += 1\n",
    "            for node in [q[head].left, q[head].right]:\n",
    "                if node is not None:\n",
    "                    q.append(node)\n",
    "                    level.append(level[head] + 1)\n",
    "                    if level[-1] >= len(max_value):\n",
    "                        max_value.append(node.val)\n",
    "                    else:\n",
    "                        max_value[level[-1]] = max(\n",
    "                            max_value[level[-1]],\n",
    "                            node.val,\n",
    "                        )\n",
    "        return max_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        \n",
    "        old_line = []\n",
    "        new_line = [root]\n",
    "        max_values = []\n",
    "        while new_line:\n",
    "            old_line = new_line\n",
    "            new_line = []\n",
    "            values = []\n",
    "            while old_line:\n",
    "                node = old_line.pop(0)\n",
    "                values.append(node.val)\n",
    "                if node.left:\n",
    "                    new_line.append(node.left)\n",
    "                if node.right:\n",
    "                    new_line.append(node.right)\n",
    "            max_values.append(max(values))\n",
    "        return max_values\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        queue = []\n",
    "        queue.append((root, 0))\n",
    "        level_max = []\n",
    "        while len(queue) > 0:\n",
    "            curr, level = queue[0]\n",
    "            del queue[0]\n",
    "            if level == len(level_max):\n",
    "                level_max.append(curr.val)\n",
    "            else:\n",
    "                level_max[level] = max(level_max[level], curr.val)\n",
    "            if curr.left is not None:\n",
    "                queue.append((curr.left, level + 1))\n",
    "            if curr.right is not None:\n",
    "                queue.append((curr.right, level + 1))\n",
    "        return level_max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        ans=[]\n",
    "        q=deque()\n",
    "        if not root:\n",
    "             return []\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            max_v = -float(\"inf\")\n",
    "            for _ in range(len(q)):\n",
    "               \n",
    "               node=q.popleft()\n",
    "               max_v=max(max_v,node.val)\n",
    "               if node.left:\n",
    "                    q.append(node.left)\n",
    "               if node.right:\n",
    "                    q.append(node.right)\n",
    "            ans.append(max_v)\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        #层序遍历\n",
    "        queue = [root]\n",
    "        result = []\n",
    "        if root == None:\n",
    "            return []\n",
    "        while queue!=[]:\n",
    "            #一层一层输出\n",
    "            length = len(queue)\n",
    "            path = []\n",
    "            for i in range(length):\n",
    "                out = queue.pop(0)\n",
    "                path.append(out.val)\n",
    "\n",
    "                if out.left!=None:\n",
    "                    queue.append(out.left)\n",
    "                \n",
    "                if out.right!=None:\n",
    "                    queue.append(out.right)\n",
    "            result.append(max(path))\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        res = []\n",
    "        if not root:\n",
    "            return res\n",
    "        cur = [root]\n",
    "        while cur:\n",
    "            nxt = []\n",
    "            cur_max = -float(\"inf\")\n",
    "            for node in cur:\n",
    "                cur_max = max(cur_max, node.val)\n",
    "                if node.left:\n",
    "                    nxt.append(node.left)\n",
    "                if node.right:\n",
    "                    nxt.append(node.right)\n",
    "            res.append(cur_max)\n",
    "            cur = nxt\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        tmp_list = []\n",
    "        out_list = []\n",
    "        checkNum = 1\n",
    "        if root:\n",
    "            tmp_list = [root]\n",
    "        while tmp_list:\n",
    "            num_list = []\n",
    "            nextCheckNum = 0\n",
    "            for i in range(checkNum):\n",
    "                first = tmp_list.pop(0)\n",
    "                if first:\n",
    "                    num_list.append(first.val)\n",
    "                    tmp_list.append(first.left)\n",
    "                    tmp_list.append(first.right)\n",
    "                    nextCheckNum +=2\n",
    "            if len(num_list) == 0:\n",
    "                break\n",
    "            out_list.append(max(num_list))\n",
    "            checkNum = nextCheckNum\n",
    "        return out_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        res = []\n",
    "        layer = [root]\n",
    "        while layer:\n",
    "            next_layer = []\n",
    "            vals = []\n",
    "            for node in layer:\n",
    "                if not node: continue\n",
    "                vals.append(node.val)\n",
    "                if node.left:\n",
    "                    next_layer.append(node.left)\n",
    "                if node.right:\n",
    "                    next_layer.append(node.right)\n",
    "            if not vals: return res\n",
    "            res.append(max(vals))\n",
    "            layer = next_layer\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        value_at_depth = dict() # 深度为索引，存放节点的值\n",
    "        max_depth = -1\n",
    "        queue = deque([(root, 0)])\n",
    "        while queue:\n",
    "            node, depth = queue.popleft()\n",
    "            if node is not None:\n",
    "                max_depth = max(max_depth, depth)\n",
    "                if depth in value_at_depth:\n",
    "                    value_at_depth[depth] = max(node.val, value_at_depth[depth])\n",
    "                else:\n",
    "                    value_at_depth[depth] = node.val\n",
    "                queue.append((node.left, depth + 1))\n",
    "                queue.append((node.right, depth + 1))\n",
    "        return [value_at_depth[depth] for depth in range(max_depth + 1)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if root is None: return []\n",
    "        ans = []\n",
    "        q = [root]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            mx = -math.inf\n",
    "            for node in tmp:\n",
    "                mx = max(mx, node.val)\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            ans.append(mx)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root: return []\n",
    "        import collections\n",
    "        queue = collections.deque()\n",
    "        res = []\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            ans = []\n",
    "            nextlist = []\n",
    "\n",
    "            for node in queue:\n",
    "                # print(node)\n",
    "                ans.append(node.val)\n",
    "                if node.left:\n",
    "                    nextlist.append(node.left)\n",
    "                if node.right:\n",
    "                    nextlist.append(node.right)\n",
    "            queue.clear()\n",
    "            queue = collections.deque(nextlist)\n",
    "            res.append(max(ans))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        ans, stack = [], deque([root])\n",
    "        while stack:\n",
    "            len_floor = len(stack)\n",
    "            max_val = float('-inf')\n",
    "            for _ in range(len(stack)):\n",
    "                node = stack.popleft()\n",
    "                max_val = max(node.val, max_val)\n",
    "                if node.left:\n",
    "                    stack.append(node.left)\n",
    "                if node.right:\n",
    "                    stack.append(node.right)\n",
    "            ans.append(max_val)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue=[]\n",
    "        result=[]\n",
    "        queue.append(root)\n",
    "\n",
    "        while queue:\n",
    "            n=len(queue)\n",
    "            ans=float('-inf')\n",
    "            for i in range(n):\n",
    "                temp=queue.pop(0)\n",
    "                ans=max(temp.val,ans)\n",
    "                if temp.left:\n",
    "                    queue.append(temp.left)\n",
    "                if temp.right:\n",
    "                    queue.append(temp.right)\n",
    "            result.append(ans)\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        # 层序遍历 用双变量实现BFS,时间复杂度O(n) 每个节点仅会进出队列一次\n",
    "        if not root:\n",
    "            return []\n",
    "        ans = []\n",
    "        q = [root]\n",
    "        while q:# 每一层\n",
    "            maxVal = -inf\n",
    "            tmp = q #存储当前层\n",
    "            q = [] #置空下一层\n",
    "            for node in tmp:#遍历每一层\n",
    "                maxVal = max(maxVal,node.val)\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            #遍历完一层\n",
    "            ans.append(maxVal) #存储当前层的最大值\n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        levels = []\n",
    "        if not root:\n",
    "            return levels\n",
    "        queue = deque([root])\n",
    "        while queue:\n",
    "            n, level = len(queue), []\n",
    "            for i in range(n):\n",
    "                node = queue.popleft()\n",
    "                level.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            levels.append(max(level))\n",
    "        return levels"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root: return []\n",
    "        queue, res = [root], []\n",
    "        while queue:\n",
    "            tmp_queue = []\n",
    "            max_value = queue[0].val\n",
    "            while queue:\n",
    "                ptr = queue.pop(0)\n",
    "                if max_value < ptr.val:\n",
    "                    max_value = ptr.val\n",
    "                if ptr.left:\n",
    "                    tmp_queue.append(ptr.left)\n",
    "                if ptr.right:\n",
    "                    tmp_queue.append(ptr.right)\n",
    "            \n",
    "            res.append(max_value)\n",
    "            queue = tmp_queue\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        queue = []\n",
    "        queue.append((root, 0))\n",
    "        level_max = dict()\n",
    "        while len(queue) > 0:\n",
    "            curr, level = queue[0]\n",
    "            del queue[0]\n",
    "            if level not in level_max:\n",
    "                level_max[level] = curr.val\n",
    "            else:\n",
    "                level_max[level] = max(level_max[level], curr.val)\n",
    "            if curr.left is not None:\n",
    "                queue.append((curr.left, level + 1))\n",
    "            if curr.right is not None:\n",
    "                queue.append((curr.right, level + 1))\n",
    "        res = []\n",
    "        for i in range(len(level_max)):\n",
    "            res.append(level_max[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = [root]\n",
    "        ans = [root.val]\n",
    "        \n",
    "        while queue:\n",
    "            res = -inf\n",
    "            tmp = queue\n",
    "            queue = []\n",
    "            for point in tmp:\n",
    "                if point.left:\n",
    "                    res = max(point.left.val,res)\n",
    "                    queue.append(point.left)\n",
    "                if point.right:\n",
    "                    res = max(point.right.val, res)\n",
    "                    queue.append(point.right)\n",
    "            if res != -inf:\n",
    "                ans.append(res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return list()\n",
    "        ans = list()\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            l = len(queue)\n",
    "            tmp = float(-inf)\n",
    "            for _ in range(l):\n",
    "                nd = queue.pop(0)\n",
    "                if tmp < nd.val:\n",
    "                    tmp = nd.val\n",
    "                if nd.left: queue.append(nd.left)\n",
    "                if nd.right: queue.append(nd.right)\n",
    "            ans.append(tmp)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root):\n",
    "        ret, queue = [], deque()\n",
    "        if root:\n",
    "            queue.append(root)\n",
    "        while queue:\n",
    "            num = -float('inf')\n",
    "            for i in range(len(queue)):\n",
    "                q = queue.popleft()\n",
    "                num = max(num, q.val)\n",
    "                if q.left:\n",
    "                    queue.append(q.left)\n",
    "                if q.right:\n",
    "                    queue.append(q.right)\n",
    "            ret.append(num)\n",
    "        return ret\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        q= [root]\n",
    "        res =[]\n",
    "        while q!=[]:\n",
    "\n",
    "            max_res = -float('inf')\n",
    "            for i in range(len(q)):\n",
    "                now = q.pop(0)\n",
    "                max_res = max(max_res,now.val)\n",
    "                if now.left:\n",
    "                    q.append(now.left)\n",
    "                if now.right:\n",
    "                    q.append(now.right)\n",
    "            \n",
    "            res.append(max_res)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if root == None:\n",
    "            return []\n",
    "        quene = deque([root])\n",
    "        res = []\n",
    "        while quene:\n",
    "            n = len(quene)\n",
    "            max_ = -inf\n",
    "            for _ in range(n):\n",
    "                tmp = quene.popleft()\n",
    "                max_ = max(max_, tmp.val)\n",
    "                if tmp.left != None:\n",
    "                    quene.append(tmp.left)\n",
    "                if tmp.right != None:\n",
    "                    quene.append(tmp.right)\n",
    "            res.append(max_)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if root==None:\n",
    "            return []\n",
    "        q = deque([root])\n",
    "        res=[]\n",
    "        while q:\n",
    "            tmp = len(q)\n",
    "            ans=-inf\n",
    "            for _ in range(tmp):\n",
    "                node = q.popleft()\n",
    "                ans = max(ans, node.val)\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            res.append(ans)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        # ans = []\n",
    "        # def get_ans(node:TreeNode, curHeight):\n",
    "        #     if node is None:\n",
    "        #         return\n",
    "        #     if curHeight == len(ans):\n",
    "        #         ans.append(node.val)\n",
    "        #     else:\n",
    "        #         # if ans[curHeight] < node.val:\n",
    "        #         #     ans[curHeight] = node.val\n",
    "        #         ans[curHeight] = max(ans[curHeight], node.val)\n",
    "        #     get_ans(node.left, curHeight+1)\n",
    "        #     get_ans(node.right, curHeight+1)\n",
    "        # get_ans(root, 0)\n",
    "        # return ans\n",
    "        node_list = [root]\n",
    "        ans = []\n",
    "        while len(node_list) >0 and node_list[0]:\n",
    "            ans.append(node_list[0].val)\n",
    "            node_list_temp = []\n",
    "            for node in node_list:\n",
    "                ans[-1] = max(ans[-1], node.val)\n",
    "                if node.left:\n",
    "                    node_list_temp.append( node.left)\n",
    "                if node.right:\n",
    "                    node_list_temp.append( node.right)\n",
    "            node_list = node_list_temp\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        ans = [root.val]\n",
    "        q = [root]\n",
    "        while q:\n",
    "            nxt = []\n",
    "            t = -float('inf')\n",
    "            for node in q:\n",
    "                if node.left:\n",
    "                    nxt.append(node.left)\n",
    "                    t = max(t, node.left.val)\n",
    "                if node.right:\n",
    "                    nxt.append(node.right)\n",
    "                    t = max(t, node.right.val)\n",
    "            q = nxt\n",
    "            ans.append(t)\n",
    "        return ans[:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        \n",
    "        results = []\n",
    "        que = deque()\n",
    "        que.append(root)\n",
    "\n",
    "        while que:\n",
    "            result = []\n",
    "            for _ in range(len(que)):\n",
    "                node = que.popleft()\n",
    "                result.append(node.val)\n",
    "                if node.left:\n",
    "                    que.append(node.left)\n",
    "                if node.right:\n",
    "                    que.append(node.right)\n",
    "            results.append(max(result))\n",
    "        \n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        res = list()\n",
    "        q = deque([root])\n",
    "\n",
    "        while q:\n",
    "            tmp = -inf\n",
    "            length = len(q)\n",
    "            for _ in range(length):\n",
    "                root = q.popleft()\n",
    "                tmp = max(tmp, root.val)\n",
    "                if root.left:\n",
    "                    q.append(root.left)\n",
    "                if root.right:\n",
    "                    q.append(root.right)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        ans = []\n",
    "        q = [root]\n",
    "        while q:\n",
    "            maxVal = -inf\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                maxVal = max(maxVal, node.val)\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            ans.append(maxVal)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        level = [root]\n",
    "        res = []\n",
    "        while level:\n",
    "            tmp = float('-inf')\n",
    "            nextLevel = []\n",
    "            for node in level:\n",
    "                if node.left:\n",
    "                    nextLevel.append(node.left)\n",
    "                if node.right:\n",
    "                    nextLevel.append(node.right)\n",
    "                tmp = max(tmp, node.val)\n",
    "            res.append(tmp)\n",
    "            level = nextLevel\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        res, queue = [],[]\n",
    "        queue.append(root)\n",
    "\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(max(tmp))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        result_list = []\n",
    "\n",
    "        curr_node_list = [root]\n",
    "        while curr_node_list:\n",
    "            next_level_node_list=[]\n",
    "            current_node_val_list=[]\n",
    "            for node in curr_node_list:\n",
    "                if not node:\n",
    "                    continue\n",
    "                current_node_val_list.append(node.val)\n",
    "                if node.left:\n",
    "                    next_level_node_list.append(node.left)\n",
    "                if node.right:\n",
    "                    next_level_node_list.append(node.right)\n",
    "            if current_node_val_list:\n",
    "                result_list.append(max(current_node_val_list))\n",
    "            curr_node_list=next_level_node_list\n",
    "\n",
    "\n",
    "        return result_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "\n",
    "        res, queue = [], [root]\n",
    "        if not root:\n",
    "            return res\n",
    "        \n",
    "        while queue:\n",
    "            tmp = []\n",
    "            max_v = float(\"-inf\")\n",
    "            for node in queue:\n",
    "                if node.left:\n",
    "                    tmp.append(node.left)\n",
    "                if node.right:\n",
    "                    tmp.append(node.right)\n",
    "\n",
    "                max_v = max(max_v, node.val)\n",
    "            res.append(max_v)\n",
    "            queue = tmp\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        ans = []\n",
    "        q = [root]\n",
    "        while q:\n",
    "            temp = q\n",
    "            q = []\n",
    "            max_temp = -inf\n",
    "            for node in temp:\n",
    "                max_temp = max(max_temp, node.val)\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            ans.append(max_temp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        res = []\n",
    "        while queue:\n",
    "            temmax = -float(\"inf\")\n",
    "            for _ in range(len(queue)):\n",
    "                tem = queue.popleft()\n",
    "                temmax = max(temmax, tem.val)\n",
    "                if tem.left:\n",
    "                    queue.append(tem.left)\n",
    "                if tem.right:\n",
    "                    queue.append(tem.right)\n",
    "            res.append(temmax)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        res,deq =[],collections.deque([root])\n",
    "        while deq:\n",
    "            l = len(deq)\n",
    "            max_value = -inf\n",
    "            for _ in range(l):\n",
    "                node = deq.popleft()\n",
    "                max_value = max(node.val,max_value)\n",
    "                if node.left: deq.append(node.left)\n",
    "                if node.right: deq.append(node.right)\n",
    "            res.append(max_value)\n",
    "        return res\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if root == None:\n",
    "            return []\n",
    "        quene = deque([root])\n",
    "        res = []\n",
    "        while quene:\n",
    "            n = len(quene)\n",
    "            max_ = -inf\n",
    "            for _ in range(n):\n",
    "                tmp = quene.popleft()\n",
    "                max_ = max(max_, tmp.val)\n",
    "                if tmp.left != None:\n",
    "                    quene.append(tmp.left)\n",
    "                if tmp.right != None:\n",
    "                    quene.append(tmp.right)\n",
    "            res.append(max_)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "\n",
    "        stack = [root]\n",
    "        ret = []\n",
    "        if not root: return ret\n",
    "        while stack:\n",
    "            tmp = []\n",
    "            ret.append(-float('inf'))\n",
    "            for s in stack:\n",
    "                if s.left: tmp.append(s.left)\n",
    "                if s.right: tmp.append(s.right)\n",
    "                ret[-1] = max(ret[-1], s.val)\n",
    "            stack = tmp[:]\n",
    "        return ret\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = []\n",
    "        result = []\n",
    "\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            maxn = -inf\n",
    "            length = len(queue)\n",
    "            print(length)\n",
    "            for i in range(length):\n",
    "                node = queue.pop(0)\n",
    "                if not node:\n",
    "                    continue\n",
    "                print(node.val)\n",
    "                if node.val > maxn:\n",
    "                    maxn = node.val\n",
    "\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            print(maxn)\n",
    "            print(\"a\\n\")\n",
    "            result.append(maxn)\n",
    "\n",
    "        return result\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import queue\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if root == None:\n",
    "            return []\n",
    "        result = []\n",
    "        q1,q2 = queue.Queue(),queue.Queue()\n",
    "        q1.put(root)\n",
    "        while not q1.empty() or not q2.empty():\n",
    "            max = float(\"-inf\")\n",
    "            if not q1.empty():\n",
    "                while not q1.empty():\n",
    "                    tmp = q1.get()\n",
    "                    if tmp.val>max:\n",
    "                        max=tmp.val\n",
    "                    if tmp.left:\n",
    "                        q2.put(tmp.left)\n",
    "                    if tmp.right:\n",
    "                        q2.put(tmp.right)\n",
    "                result.append(max)\n",
    "\n",
    "            elif not q2.empty():\n",
    "                while not q2.empty():\n",
    "                    tmp = q2.get()\n",
    "                    if tmp.val>max:\n",
    "                        max=tmp.val\n",
    "                    if tmp.left:\n",
    "                        q1.put(tmp.left)\n",
    "                    if tmp.right:\n",
    "                        q1.put(tmp.right)\n",
    "                result.append(max)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root: return []\n",
    "        seq=collections.deque([root])\n",
    "        ans=[]\n",
    "        while seq:\n",
    "            n=len(seq)\n",
    "            maxval=-float('inf')\n",
    "            for i in range(n):\n",
    "                valnow=seq.popleft()\n",
    "                maxval=max(valnow.val, maxval)\n",
    "                if valnow.right:seq.append(valnow.right)\n",
    "                if valnow.left:seq.append(valnow.left)\n",
    "            ans.append(maxval)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\r\n",
    "        if not root:\r\n",
    "            return []\r\n",
    "        res=[]\r\n",
    "        node=[]\r\n",
    "        # 接下来进行层次遍历\r\n",
    "        node.append(root)\r\n",
    "        while node:\r\n",
    "            max_val=float('-inf')\r\n",
    "            new_node=[]\r\n",
    "            for i in range(len(node)):\r\n",
    "                max_val=max(max_val,node[i].val)\r\n",
    "                if node[i].left:\r\n",
    "                    new_node.append(node[i].left)\r\n",
    "                if node[i].right:\r\n",
    "                    new_node.append(node[i].right)\r\n",
    "            res.append(max_val)\r\n",
    "            node=new_node\r\n",
    "        return res\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        result = []\n",
    "        qa = deque()\n",
    "        qb = deque()\n",
    "        if not  root:\n",
    "            return result\n",
    "\n",
    "        qa.appendleft(root)\n",
    "        # print(root)\n",
    "\n",
    "        while len(qa) > 0 or len(qb) > 0:\n",
    "            max_val = float(\"-inf\")\n",
    "            while len(qa) > 0:\n",
    "                node = qa.pop()\n",
    "                if node.val is not None:\n",
    "                    max_val = max(max_val, node.val)\n",
    "                if node.left:\n",
    "                    qb.appendleft(node.left)\n",
    "                if node.right:\n",
    "                    qb.appendleft(node.right)\n",
    "            result.append(max_val)\n",
    "            t = qa\n",
    "            qa = qb\n",
    "            qb = t\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        ret, queue = [], deque()\n",
    "        if root:\n",
    "            queue.append(root)\n",
    "        while queue:\n",
    "            num = -float('inf')\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                num = max(num, node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            ret.append(num)\n",
    "        return ret        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if root == None:\n",
    "            return []\n",
    "        quene = deque([root])\n",
    "        res = []\n",
    "        while quene:\n",
    "            n = len(quene)\n",
    "            max_ = -inf\n",
    "            for _ in range(n):\n",
    "                tmp = quene.popleft()\n",
    "                max_ = max(max_, tmp.val)\n",
    "                if tmp.left != None:\n",
    "                    quene.append(tmp.left)\n",
    "                if tmp.right != None:\n",
    "                    quene.append(tmp.right)\n",
    "            res.append(max_)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        ans = []\n",
    "        if not root:\n",
    "            return ans\n",
    "        q = deque([root])\n",
    "        tempq = deque()\n",
    "        count = -inf\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            count = max(count, node.val)\n",
    "            if node.left:\n",
    "                tempq.append(node.left)\n",
    "            if node.right:\n",
    "                tempq.append(node.right)\n",
    "            if not q:\n",
    "                q = tempq\n",
    "                tempq = deque()\n",
    "                ans.append(count)\n",
    "                count = -inf\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        d = collections.deque()\n",
    "        d.append((root, 0))\n",
    "        ans = [root.val]\n",
    "        while d:\n",
    "            cur, layer = d.popleft()\n",
    "            if cur.left:\n",
    "                d.append((cur.left, layer+1))\n",
    "            if cur.right:\n",
    "                d.append((cur.right, layer+1))\n",
    "            \n",
    "            if layer == len(ans):\n",
    "                ans.append(cur.val)\n",
    "            else:\n",
    "                ans[layer] = max(ans[layer], cur.val)\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        res = []\n",
    "        q = collections.deque()\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            n = len(q)\n",
    "            mx = -2147483648\n",
    "            for _ in range(n):\n",
    "                node = q.popleft()\n",
    "                mx = max(node.val, mx)\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            res.append(mx)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root: return []\n",
    "        seq=collections.deque()\n",
    "        seq.append(root)\n",
    "        ans=[]\n",
    "        while seq:\n",
    "            n=len(seq)\n",
    "            maxval=-float('inf')\n",
    "            for i in range(n):\n",
    "                valnow=seq.popleft()\n",
    "                maxval=max(valnow.val, maxval)\n",
    "                if valnow.right:seq.append(valnow.right)\n",
    "                if valnow.left:seq.append(valnow.left)\n",
    "            ans.append(maxval)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        ans=[]\n",
    "        if not root: return ans\n",
    "        seq=collections.deque([root])\n",
    "        while seq:\n",
    "            n=len(seq)\n",
    "            maxval=-float('inf')\n",
    "            for i in range(n):\n",
    "                valnow=seq.popleft()\n",
    "                maxval=max(valnow.val, maxval)\n",
    "                if valnow.right:seq.append(valnow.right)\n",
    "                if valnow.left:seq.append(valnow.left)\n",
    "            ans.append(maxval)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        ans = []\n",
    "        def dfs(cur, k):\n",
    "            if not cur:\n",
    "                k -= 1\n",
    "                return\n",
    "            if k == len(ans):\n",
    "                ans.append(cur.val)\n",
    "            else:\n",
    "                ans[k] = max(ans[k], cur.val)\n",
    "            k += 1\n",
    "            dfs(cur.left, k)\n",
    "            dfs(cur.right, k)\n",
    "        dfs(root, 0)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ans = []\n",
    "\n",
    "        def dfs(node:TreeNode, curHeight:int):\n",
    "            if node is None:\n",
    "                return \n",
    "            if curHeight == len(ans):\n",
    "                # 第index层对应的ans中的位置为空时，先填充第一个值\n",
    "                ans.append(node.val)\n",
    "            else:\n",
    "                # 第index层对应的ans中的位置不为空时，取该层的最大值作为该层最终填充值\n",
    "                ans[curHeight] = max(ans[curHeight], node.val)\n",
    "            dfs(node.left, curHeight + 1)\n",
    "            dfs(node.right, curHeight + 1)\n",
    "        dfs(root, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        ans = []\n",
    "        def get_ans(node:TreeNode, curHeight):\n",
    "            if node is None:\n",
    "                return\n",
    "            if curHeight == len(ans):\n",
    "                ans.append(node.val)\n",
    "            else:\n",
    "                if ans[curHeight] < node.val:\n",
    "                    ans[curHeight] = node.val\n",
    "            get_ans(node.left, curHeight+1)\n",
    "            get_ans(node.right, curHeight+1)\n",
    "        get_ans(root, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        ret = [[root.val]]\n",
    "        queue = [(root, 0)]\n",
    "        head = 0\n",
    "        tail = 1\n",
    "        while head < tail:\n",
    "            if queue[head][0].left:\n",
    "                queue.append((queue[head][0].left, queue[head][1] + 1))\n",
    "                tail += 1\n",
    "            if queue[head][0].right:\n",
    "                queue.append((queue[head][0].right, queue[head][1] + 1))\n",
    "                tail += 1\n",
    "            head += 1\n",
    "        for i in range(1,tail):\n",
    "            if queue[i][1] == queue[i - 1][1]:\n",
    "                ret[queue[i][1]].append(queue[i][0].val)\n",
    "            else:\n",
    "                ret.append([queue[i][0].val])\n",
    "        for i in range(len(ret)):\n",
    "            ret[i] = max(ret[i])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        ans=[]\n",
    "        def dfs(node: TreeNode, curHeight: int):\n",
    "            if node is None:\n",
    "                return  None\n",
    "            if curHeight == len(ans):\n",
    "                ans.append(node.val)\n",
    "            else:\n",
    "                ans[curHeight] = max(ans[curHeight], node.val)\n",
    "            dfs(node.left, curHeight+1)\n",
    "            dfs(node.right, curHeight + 1)\n",
    "        dfs(root, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        ans = []\n",
    "        def dfs(node: TreeNode, curHeight: int) -> None:\n",
    "            if node is None:\n",
    "                return\n",
    "            if curHeight == len(ans):\n",
    "                ans.append(node.val)\n",
    "            else:\n",
    "                ans[curHeight] = max(ans[curHeight], node.val)\n",
    "            dfs(node.left, curHeight + 1)\n",
    "            dfs(node.right, curHeight + 1)\n",
    "        dfs(root, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestValues(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ans = []\n",
    "        def dfs(node: TreeNode, curHeight: int) -> None:\n",
    "            if node is None:\n",
    "                return\n",
    "            if curHeight == len(ans):\n",
    "                ans.append(node.val)\n",
    "            else:\n",
    "                ans[curHeight] = max(ans[curHeight], node.val)\n",
    "            dfs(node.left, curHeight + 1)\n",
    "            dfs(node.right, curHeight + 1)\n",
    "        dfs(root, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        ans = []\n",
    "        def get_ans(node:TreeNode, curHeight):\n",
    "            if node is None:\n",
    "                return\n",
    "            if curHeight == len(ans):\n",
    "                ans.append(node.val)\n",
    "            else:\n",
    "                # if ans[curHeight] < node.val:\n",
    "                #     ans[curHeight] = node.val\n",
    "                ans[curHeight] = max(ans[curHeight], node.val)\n",
    "            get_ans(node.left, curHeight+1)\n",
    "            get_ans(node.right, curHeight+1)\n",
    "        get_ans(root, 0)\n",
    "        return ans\n",
    "        # node_list = [root]\n",
    "        # ans = []\n",
    "        # while len(node_list) > 0:\n",
    "        #     ans.append(node[0].val)\n",
    "        #     for node in node_list:\n",
    "        #         if "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues2(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return list()\n",
    "        ans = list()\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            l = len(queue)\n",
    "            tmp = float(-inf)\n",
    "            for _ in range(l):\n",
    "                nd = queue.pop(0)\n",
    "                if tmp < nd.val:\n",
    "                    tmp = nd.val\n",
    "                if nd.left: queue.append(nd.left)\n",
    "                if nd.right: queue.append(nd.right)\n",
    "            ans.append(tmp)\n",
    "        return ans\n",
    "\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        ans = list()\n",
    "        if root:\n",
    "            def dfs(root, depth):\n",
    "                if root:\n",
    "                    if len(ans) == depth:\n",
    "                        ans.append(root.val)\n",
    "                    if ans[depth] < root.val: ans[depth] = root.val\n",
    "                    if root.left: dfs(root.left, depth + 1)\n",
    "                    if root.right: dfs(root.right, depth + 1)\n",
    "\n",
    "            dfs(root,0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ans = []\n",
    "        def dfs(node: TreeNode, curHeight: int) -> None:\n",
    "            if node is None:\n",
    "                return\n",
    "            if curHeight == len(ans):\n",
    "                ans.append(node.val)\n",
    "            else:\n",
    "                ans[curHeight] = max(ans[curHeight], node.val)\n",
    "            dfs(node.left, curHeight + 1)\n",
    "            dfs(node.right, curHeight + 1)\n",
    "        dfs(root, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        ans=[]\n",
    "        def dfs(node: TreeNode, curHeight: int):\n",
    "            if node is None:\n",
    "                return  None\n",
    "            if curHeight == len(ans):\n",
    "                ans.append(node.val)\n",
    "            else:\n",
    "                ans[curHeight] = max(ans[curHeight], node.val)\n",
    "            dfs(node.left, curHeight+1)\n",
    "            dfs(node.right, curHeight + 1)\n",
    "        dfs(root, 0)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
